home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programmierung
/
Power-Programmierung (Tewi)(1994).iso
/
magazine
/
drdobbs
/
1991
/
04
/
morrow
/
popl.c
< prev
next >
Wrap
C/C++ Source or Header
|
1989-09-03
|
6KB
|
304 lines
/***
* GASystem
* Mike Morrow
* September 1989
***/
/**
* Routines to deal with the population of genes
**/
#include "ga.h"
#include "param.h"
#include "gene.h"
#include "util.h"
extern void *calloc();
#if __STDC__
static int cmpints(GENE **g1, GENE **g2);
#else
static int cmpints();
#endif
#ifndef TRUE
# define TRUE 1
# define FALSE 0
#endif
/**
*
*
**/
static GENE **population, **newpopl;
/**
* poplstart is FALSE until somebody calls poplopen(). The population
* manipulation functions won't do anything until poplstart is TRUE.
* This allows various parameters to be set without continually regenerating
* populations.
**/
static short int poplstart = FALSE;
/**
* These variables hold parameters that the user may set by interacting with the
* symbol table. The default values are hardwired here.
**/
static int param_popl_size = 100; /* population size */
static FIT_TYPE param_popl_fitness = 0; /* sum of fitnesses */
static int param_popl_mu = 1000; /* inverse of prob. of mutation */
static int param_popl_nmu = 0; /* number of mutations so far */
static CONST PARAMSPEC poplparams[] =
{
{"POP", (void *) ¶m_popl_size, MODEINT, FLAG_INIT},
{"FIT", (void *) ¶m_popl_fitness, MODEFIT, FLAG_RO},
{"MU", (void *) ¶m_popl_mu, MODEINT, },
{"NMU", (void *) ¶m_popl_nmu, MODEINT, FLAG_RO },
{(char *) 0, (void *) 0, (MODE) 0, 0 }
};
/**
* This routine inserts information about the parameter vars
* into the symbol table.
**/
poplpinit()
{
CONST PARAMSPEC *p;
for(p = poplparams; p->param_name; p++)
paramins(p, SYMVAR);
}
/**
* Free old population.
**/
poplfree()
{
unsigned int i;
if(population)
{
warning("Destroying old population...");
for(i = 0; i < param_popl_size; i++)
{
free(population[i]);
free(newpopl[i]);
}
}
population = newpopl = (GENE **) 0;
param_popl_nmu = 0;
}
poplopen()
{
poplstart = TRUE;
poplinit();
popleval();
}
/**
* Initialize the population of genes
**/
poplinit()
{
unsigned int i;
if(! poplstart)
return ;
population = calloc(param_popl_size, sizeof(GENE *));
newpopl = calloc(param_popl_size, sizeof(GENE *));
if(! population || ! newpopl)
{
fatal("No memory for population");
}
for(i = 0; i < param_popl_size; i++)
if(! (population[i] = genenew()) || ! (newpopl[i] = genenew()))
{
char buff[80];
sprintf(buff, "No memory to generate population of size %d\n",
param_popl_size);
fatal(buff);
}
}
/**
* Pass each member of the population through the objective function.
* This function also accumulates a new value for param_popl_fitness.
**/
popleval()
{
unsigned int i;
if(! poplstart)
return ;
param_popl_fitness = 0;
for(i = 0; i < param_popl_size; i++)
param_popl_fitness += genefitness(population[i]);
}
/**
* Show the top n members of the population
**/
void popldump(n)
int n;
{
unsigned int i;
qsort(population, param_popl_size, sizeof(GENE *), genecomp);
if(! n)
n = param_popl_size;
for(i = 0; i < n; i++)
geneshow(population[i]);
objdumpdone();
}
/**
* Do reproduction
**/
void poplrepro()
{
register FIT_TYPE ave_fit;
register unsigned int oldindex, newindex;
GENE **temp;
#define SCALE (FIT_TYPE) 128
/**
* ave_fit gets a value that represents the average fitness of all
* the genes. ave_fit is actually scaled to be (ave_fitness * SCALE).
**/
ave_fit = SCALE * param_popl_fitness;
ave_fit /= param_popl_size;
newindex = oldindex = 0;
if(ave_fit > 0) /* don't do reproduction in degenerate case */
{
/**
* Keep selecting genes for replication until we've filled up the
* newpopl[] population.
**/
while(newindex < param_popl_size)
{
FIT_TYPE chance;
/**
* chance gets a value that represents how this gene's fitness
* compares to the average fitness. chance is scaled so that
* an a gene with average fitness will have chance = SCALE.
**/
chance = SCALE * SCALE * population[oldindex]->gene_fit;
chance /= ave_fit;
/**
* Generate a random number in [0, 2 * SCALE]. If the gene is
* of average fitness, it will have a 50-50 chance
* of duplicating.
**/
if(chance >= randnum((int)SCALE * 2))
{
genedupl(newpopl[newindex++], population[oldindex]);
}
/**
* Go to the next candidate in the old population. We may have
* to wrap back to the beginning.
**/
oldindex++;
if(oldindex == param_popl_size)
oldindex = 0;
}
}
/**
* Switch around -- the new population becomes the current population.
**/
temp = population;
population = newpopl;
newpopl = temp;
}
/**
* Do mutation
**/
poplmutate()
{
unsigned int i;
for(i = 0; i < param_popl_size; i++)
if(! randnum(param_popl_mu))
{
param_popl_nmu++;
genemutate(population[i]);
}
}
/**
* Do crossover
**/
void poplcross()
{
unsigned int i;
/**
* First, put the poplulation into random order.
**/
for(i = 0; i < param_popl_size; i++)
population[i]->gene_tag = rand();
qsort(population, param_popl_size, sizeof(GENE *), cmpints);
/**
* Then pair up the genes for crossover.
**/
for(i = 0; i + 1 < param_popl_size; i += 2)
{
genecross(population[i], population[i+1]);
}
}
/**
* Used by poplcross() in the call to qsort().
**/
static int cmpints(g1, g2)
GENE **g1, **g2;
{
return (*g2)->gene_tag - (*g1)->gene_tag;
}